//用栈实现队列
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <Stdbool.h>
typedef int STDataType;

typedef struct Stack
{
	STDataType* _a;	
	int _top;//栈顶下标
	int _capacity;
}Stack;


//初始化
	void StackInit(Stack* pst)
	{
		assert(pst);
		pst->_a = malloc(sizeof(STDataType) * 4);
		pst->_top = 0;
		pst->_capacity = 4;
	}
	//销毁栈
	void StackDestory(Stack* pst)
	{
		assert(pst);
		free(pst->_a);
		pst->_a = NULL;
	}
	//入栈
	void StackPush(Stack* pst, STDataType x)
	{
		assert(pst);
		if (pst->_top == pst->_capacity)
		{
			pst->_capacity *= 2;
			STDataType* tmp = (STDataType*)realloc(pst->_a, sizeof(STDataType)*pst->_capacity);
			pst->_a = tmp;
		}
		pst->_a[pst->_top] = x;
		pst->_top++;
	}
	//出栈
	void StackPop(Stack* pst)
	{
		assert(pst);
		assert(pst->_top > 0);
		--pst->_top;//直接让top减一，意思是让栈顶的元素为要删除的元素的上一个数
		//原来的栈顶就不用管了

	}
	//返回栈的大小
	int StackSize(Stack* pst)
	{
		assert(pst);
		return pst->_top;
	}
	//判断栈是否为空 返回1为空，返回0为非空。
	int StackEmpty(Stack* pst)
	{
		return pst->_top == 0 ? 1 : 0;
	}
	//返回栈顶的数据
	STDataType StackTop(Stack* pst)
	{
		assert(pst);
		assert(pst->_top > 0);
		return pst->_a[pst->_top-1];
	}   
typedef struct {    
    Stack _pushST;
    Stack _popST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* Queue=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&Queue->_pushST);
    StackInit(&Queue->_popST);
    return Queue;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->_pushST,x);
}



int myQueuePeek(MyQueue* obj) {
    if(!StackEmpty(&obj->_popST))
    {
        return StackTop(&obj->_popST);
    }
    else
    {
        while(!StackEmpty(&obj->_pushST))
        {
            StackPush(&obj->_popST,StackTop(&obj->_pushST));
            StackPop(&obj->_pushST);
        }
        return StackTop(&obj->_popST);
    }
}

int myQueuePop(MyQueue* obj) {
    int ret=myQueuePeek(obj);
    StackPop(&obj->_popST);
    return ret;
}

bool myQueueEmpty(MyQueue* obj) {
        return StackEmpty(&obj->_pushST)&& StackEmpty(&obj->_popST);
    
}

void myQueueFree(MyQueue* obj) {
    StackDestory(&obj->_pushST);
    StackDestory(&obj->_popST);

    free(obj);
}

bool isValid(char* s) 
{
    Stack st;
    StackInit(&st);
    bool ret;
    while(*s!='\0')
    {
        if(*s=='('||*s=='{'||*s=='[')
        {
            StackPush(&st,*s);
            s++;
        }
        else
        {
            if(StackEmpty(&st))
            {
                ret =false;
                break;
            }
            char top=StackTop(&st);
            if(*s==')'&&top!='(')
            {
                ret=false;
                break;
            }
            if(*s==']'&&top!='[')
            {
                ret=false;
                break;
            }
            if(*s=='}'&&top!='{')
            {
                ret=false;
                break;
            }
            StackPop(&st);
            s++;
        }

    }
    if(*s=='\0')
    {
        ret=StackEmpty(&st);    
    }
    StackDestory(&st);
    return ret;        
}